package trie

import "fmt"

type ACTrie struct {
	root *ACNode
}

type ACNode struct {
	char     rune
	children []*ACNode
	isEnding bool
	fail     *ACNode
	count    int
	charStr  string
}

func (this *ACTrie) insert(str string) {

	chars := []rune(str)

	p := this.root
	i := 0
	for ; i < len(chars); i++ {

		index := chars[i] - 'a'

		if p.children[index] == nil {
			p.children[index] = &ACNode{char: chars[i], isEnding: false, children: make([]*ACNode, 26), count: -1, charStr: string(chars[i])}
		}

		p = p.children[index]
	}
	p.isEnding = true
	p.count = i
}

func (this *ACTrie) match(pattern string) { // text 是主串

	patternStr := []rune(pattern)
	n := len(patternStr)

	p := this.root
	for i := 0; i < n; i++ {

		idx := patternStr[i] - 'a'

		for p.children[idx] == nil && p != this.root {
			p = p.fail // 失败指针发挥作用的地方
		}

		p = p.children[idx]
		if p == nil {
			p = this.root // 如果没有匹配的，从 root 开始重新匹配
		}

		tmp := p

		for tmp != this.root { // 打印出可以匹配的模式串
			if tmp.isEnding {

				pos := i - tmp.count + 1

				fmt.Printf("匹配到的字符串 : %s ,匹配起始下标 : %d,长度 : %d \n", pattern[pos:tmp.count+pos], pos, tmp.count)
			}
			tmp = tmp.fail
		}
	}
}

func (this *ACTrie) string() {

	p := this.root

	fmt.Println(string(p.char))

	this.print(p)
}

func (this *ACTrie) print(p *ACNode) {

	for _, treeNode := range p.children {

		if treeNode != nil {
			fmt.Printf("当前指针 : %s ,错误指针 : %s   \n", string(treeNode.char), string(treeNode.fail.char))
			this.print(treeNode)
		}

	}

	if p.count > - 1 {

		fmt.Println()
	}
}

func (this ACTrie) buildFailurePointer() {

	queue := make(chan *ACNode, 1000)

	this.root.fail = nil

	queue <- this.root

	for len(queue) != 0 {
		p := <-queue
		for i := 0; i < 26; i++ {
			pc := p.children[i]
			if pc == nil {
				continue
			}

			if p == this.root {
				pc.fail = this.root
			} else {
				q := p.fail
				for q != nil {

					qc := q.children[pc.char-'a']
					if qc != nil {
						pc.fail = qc
						break
					}
					q = q.fail
				}
				if q == nil {
					pc.fail = this.root
				}
			}
			queue <- pc

		}
	}
}
